#https://leetcode.cn/problems/count-number-of-ways-to-place-houses/submissions/562697414/

const int MOD = 1e9 + 7, MX = 1e4 + 1;// 定义数组的最大长度
// 静态初始化斐波那契数列
int f[MX] = {1, 2};
// 静态初始化函数，计算斐波那契数列
int init = []() {
     // 从第三个元素开始填充 f 数组
    for (int i = 2; i < MX; ++i)
    // 根据斐波那契数列定义计算当前值
        f[i] = (f[i - 1] + f[i - 2]) % MOD;
    return 0;
}();

class Solution {
public:
    int countHousePlacements(int n) {
        return (long) f[n] * f[n] % MOD;
    }
};